package demo1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //全排列 2
    List<List<Integer>> retPermute ;
    List<Integer> path1;
    boolean[] check;
    HashSet<List<Integer>> set;
    public List<List<Integer>> permuteUnique1(int[] nums) {
        check = new boolean[nums.length];
        retPermute = new ArrayList<>();
        path1 = new ArrayList<>();
        set = new HashSet<>();
        dfs1(nums);
        return retPermute;
    }

    private void dfs1(int[] nums){
        if(path1.size() == nums.length && !set.contains(new ArrayList<>(path1))){
            List<Integer> pcur = new ArrayList<>(path1);
            set.add(pcur);
            retPermute.add(pcur);
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(check[i] == false){
                path1.add(nums[i]);
                check[i] = true;
                dfs1(nums);
                path1.remove(path1.size()-1);
                check[i] = false;
            }
        }
    }

    //子集
    List<List<Integer>> retSubsets;
    List<Integer> path;
    public List<List<Integer>> subsets(int[] nums) {
        retSubsets = new ArrayList<>();
        path = new ArrayList<>();
        dfs3(nums,0);
        return retSubsets;
    }

    private void dfs3 (int[] nums, int pos){
        List<Integer> pcur = new ArrayList<>(path);
        retSubsets.add(pcur);
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfs3(nums,i+1);
            path.remove(path.size()-1);
        }
    }

    //全排列 2（优化）
    List<List<Integer>> ret;
    boolean[] check2 ;
    List<Integer> getPath ;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        ret = new ArrayList<>();
        getPath = new ArrayList<>();
        check2 = new boolean[nums.length];
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums){
        if(getPath.size() == nums.length){
            ret.add(new ArrayList<>(getPath));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(check2[i] == false && (i==0 || nums[i] != nums[i-1] || check2[i-1] == true)){
                getPath.add(nums[i]);
                check2[i] = true;
                dfs(nums);
                getPath.remove(getPath.size()-1);
                check2[i] = false;
            }
        }
    }
}















